package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 循环链表
 * @date 2022/9/3 13:18
 */
public class Demo32 {

    /**
     * Definition for singly-linked list.
     * */
     class ListNode {
         int val;
         ListNode next;
         ListNode(int x) {
             val = x;
             next = null;
         }
     }
    public ListNode detectCycle(ListNode head) {

        if(head==null||head.next==null){
            return null;
        }
        boolean flag=false;
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                flag=true;
                break;
            }
        }
        //判断是否存在环，存在环再去判断入口
        //快慢指针相遇肯定在环上，假设起点到环的位置是a, 环上走了m步。环大小为b
        // 则此时慢指针位置为a+m,快指针为 2(a+m)=a+m+b(最多绕一圈就相遇了)====>a+m=b
        // 所以此时慢指针离入口还差 b-m=a 即起点到入口的距离
        ListNode root=head;
        if(flag){
           while (root!=slow){
               root=root.next;
               slow=slow.next;
           }
           return slow;
        }
        //不存在环，返回null
        return null;
    }

}
